#include "solve_bfs.h"


namespace solve_bfs_ns{
	int pd=0;
    int wkx[4] = {-1, 1,  0, 0 };
    int wky[4] = {0,  0, -1, 1 }; 
    bool judge[1000][1000];
    Queue Ansx,Ansy;
	Point father[1000][1000];
};

using namespace solve_bfs_ns;
using std::cin ;
using std::cout;
using std::endl;



void solve_bfs(int x, int y)
{
	judge[x][y]=1;
	father[x][y].x=x;	
    father[x][y].y=y;
	Ansx.push(x);
    Ansy.push(y);

	while (Ansx.Qsize())
	{
		bfsnum++;
		Point front;
        front.x=Ansx.pop(); 
		front.y=Ansy.pop();
		for (int i = 0;i < 4;i++)
		{
			int xx= front.x + wkx[i];
			int yy= front.y + wky[i];
			if (xx >= 0 && xx < row && yy >= 0 && yy < col && !judge[xx][yy] && !map[xx][yy])
			{
				bfsnum++;
				judge[xx][yy]=1;
				father[xx][yy]=front;
				Ansx.push(xx);
                Ansy.push(yy);			
		        Set_Grapics(yy*2,xx,9);cout<<"*";
				if(xx==endpoint.x&&yy==endpoint.y) 
				{
					pd=1;return;
				}
            }
		}
	}

}

void print_bfs_path(int x, int y)
{
	Stack path_x,path_y;	
    path_x.push(x);
    path_y.push(y);
	while (true)
	{
		int father_x = father[x][y].x;
		int father_y = father[x][y].y;
		if (father_x == x && father_y == y) 
		{
			break;
		}
		else 
		{
			path_x.push(father_x); 
            path_y.push(father_y); 
			x=father_x;
			y=father_y;
		}
	}
	while (path_x.Ssize())
	{
		Set_Grapics(path_y.pop()*2,path_x.pop(),12);cout<<"*";
	}
}

void print_bfs_ans(int x, int y)
{
    cout<<endl<<endl;
    if(!pd)
    {
        cout<<"No Answer!"<<endl;
        return;
    }
	Stack path_x,path_y;	
    path_x.push(x);
    path_y.push(y);
	while (true)
	{
		int father_x = father[x][y].x;
		int father_y = father[x][y].y;
		if (father_x == x && father_y == y) 
		{
			break;
		}
		else 
		{
			path_x.push(father_x); 
            path_y.push(father_y); 
			x=father_x;
			y=father_y;
		}
	}
	int sum=1;
	int tempx=1,tempy=1;
	while (path_x.Ssize()) 
	{
		int nowx=path_x.pop(),nowy=path_y.pop();
		cout<<"("<<nowx<<","<<nowy;
		if(nowx==tempx&&nowy==tempy+1)  cout<<","<<"left"<<")"<<endl;
		else if(nowx==tempx&&nowy==tempy-1)  cout<<","<<"right"<<")"<<endl;
		else if(nowx==tempx+1&nowy==tempy)   cout<<","<<"up"<<")"<<endl;
		else if(nowx==tempx-1&nowy==tempy)   cout<<","<<"down"<<")"<<endl;
		else cout<<")"<<endl;
		tempx=nowx,tempy=nowy;
		sum++;
	}
}







